Bifrost 风控系列一：对 Validators 串通作恶的分析

共享安全性的缘起

Bifrost 致力于为公链的 PoS 机制提供流动性解决方案。由于在 Bifrost 平台上，用户可以用低廉的价格购买到运行 PoS 节点所需的投票权。因此我们需要考虑购票行为对 PoS 公链安全性的影响。让我们以 Polkadot 为例进行科学的分析。

首先回顾下区块链共识机制的发展历史，PoW 作为最早出现的共识机制，伴随着比特币的出现而出现。发展至今，也只有 BTC，ETH1.0 等少数成功的项目，究其原因，全球算力资源是有限的，当大多数算力集中于比特币时，其他的 PoW 型公链便很难安全启动。由于网络不能吸引足够的算力，其安全性不堪一击，比特币网络的大矿主所掌握的算力，足以对一些较小的 PoW 网络发起 51% 攻击。

后来，人们又发明了 PoS 机制，依靠自身的有价  token 来作为维护网络安全的抵押品，使得共识过程不再需要与其他项目争夺算力。但 PoS 也并没有完全摆脱 PoW 面临的困境，因为维护一个 PoS 网络，需要基本的安全支出。当币价过低，价值捕获能力不足时，高额的通胀会将网络通向死亡螺旋。虽然  PoS 网络之间不会像 PoW 网络之间那样直接竞争算力资源。但是在特定时间点，市场上支撑币价的购买力是一定的，放大了说，世界上的经济价值总量也是一定的，不同币种之间的币价仍有一定竞争性。对于币价比较低的初创项目，其网络安全极不可靠。这一点依旧阻碍着区块链领域的创新。

面对这样的问题，波卡提出了“共享安全性”的概念。波卡通过中继链+平行链的架构，让平行链无须自身提供安全性，而可以复用波卡的安全性。因此作为波卡平行链的项目，可以专注于开发自己的业务逻辑。此外，波卡还提供了安全的跨链互操作性，平行链之间的跨链消息传递可以通过中继链安全的进行，不再需要额外的信任机制。

共享安全性的实现与问题

在讨论 Polkadot 平行链的安全性之前，我们可以先简单回顾一下 Polkadot 的体系结构设计：Polkadot 采取了 RelayChain（中继链）与 ParaChain（平行链）的系统架构，中继链的验证者（Validators）为平行链提供区块有效性和可用性验证，并采取Erasure Coding（纠删码）的方式，为平行链区块与有效性证明数据（PoV）提供存储备份。平行链节点（Collators）负责构建平行链自身的区块与账本，为外部用户提供更专业的服务。

平行链 Collators 在运行期间，中继链会根据一定的规则，随机分配多个 Validators，对 Collators 提交的区块与 PoV 进行验证，因此平行链的安全和可用性，很大程度上取决于中继链整体的安全性，以及 Validators 的安全性。若分配给某个平行链的多个 Validators 中超过半数串通作恶，则会导致该平行链在一段时间内不可用，尽管这些作恶节点会遭受中继链自身给予的惩罚（Slash）。我们可以对这种情况的概率进行数学分析。

问题描述：

假设 Polkadot 系统具备 1,000 个 Validators，100 个平行链槽位，则每个平行链平均可获得 10 个随机分配的 Validators，若其中超过 5 个恶意节点，则可成功发起对平行链的攻击。若这 1,000 个 Validators 中总计有 20 个恶意节点，该如何计算，超过 5 个恶意节点在一次分配中，被分配到同一个平行链（记为事件 E ）的概率？

这是一个很有趣的排列组合与概率计算问题。首先，将这个问题继续简化，将其等价于这个场景：N = 20（不良样本），K = 100（盒子、容器），完全随机分配，请问：6 个或以上不良样本进入同一个盒子（记为事件E）的概率是多少？这个问题本质上是有条件地对一个正整数进行加法分解。

解题思路：

采用递归降解方法，将大问题化解为小问题，大的参数转化为小的参数，最终返回结果。首先计算不发生事件 E 的排列组合数 P1，然后计算出任意的排列组合总数 P2，则1 –（P1 / P2）的值，即为结果概率值。

求解过程：

不良样本数量 N，正常样本数量 M，容器数量 K , 单个容器的不良样本数量容忍上限，单个容器填充样本数量 T ，上述参数均为正整数，问题可简记为：

P(N, M, K, T, R) => P(20, 980, 100, 10, 5)

=> [20 = i1+i2…+i100]

=> [980 = j1+j2…+j100]

=> [1000 = (i1+j1)+(i2+j2)…+(i100+j100)], in+jn = 10

jn 取值范围为 [0, 10]，in 取值范围为 [0, 5]，因为若超过 5 则发生 E 事件，不符合前提条件。根据排列组合的乘法原理，分 100 步完成加法等分任务。第1步的组合数量 C(20, i1) C(980, j1)，剩余的待解决组合数 P(20-i1, 980-j1, 99, 10, 5)，即：

P(20, 980, 100, 10, 5) =

C(20, i1)C(980, j1)P(20-i1, 980-j1, 99, 10, 5)。

按照同样的思路，接着对 P(20-i1, 980-j1, 99, 10, 5)进行求解，即：

P(20-i1, 980-j1, 99, 10, 5) =

C(20-i1-i2, i2)C(980-j1-j2, j2)P(20-i1-i2, 980-j1-j2, 99, 10, 5)

由于 jn 取值范围为 [0, 10]，in 取值范围为 [0, 5]，in+jn=10,所以根据排列组合的加法原理，C(20, i1)C(980, j1)P(20-i1, 980-j1, 99, 10, 5) 对应以下分类之和：

i1 = 0 => j1 = 10 => C(20, 0)C(980, 10)P(20, 970, 99, 10, 5)

i1 = 1 => j1 = 9 => C(20, 1)C(980, 9)P(19, 971, 99, 10, 5)

…

i1 = 5 => j1 = 5 => C(20, 5)C(980, 5)P(15, 975, 99, 10, 5)

持续迭代（递归降解）下去，直到可直接得出更小规模的 P(N, M, K, T, R)的值为止。注意 T 与 R 的值始终保持不变，KR >= N，KR >= M，K*T = N+M时，P(N, M, K, T, R)才有意义。而当 N <= R 时，R 不再有限制意义，这时恰好可以得出：

P(N, M, K, T, R) = C(KT, T)C((K-1)T, T)…C(2T, T)C(T, T)

此时一次递归调用的过程可以终结。将 P(N, M, K, T, R)的值记为 P1,任意组合值记为 P2，P2 = C(1000, 10)C((990, 10)…C(20, 10)C(10, 10)，1-(P1/P2) 即为发生事件 E 的概率值。

根据以上的问题分析与解题思路，我们可以很容易写出对应的算法程序，并计算出 1,000 个节点中有 20 个恶意节点时，可以串通起来对平行链发起有效攻击的概率值为：

0.0000005666859763811864585098205641632487151064266458860864606967870544507157082900619766159677426216；

当恶意节点数量为 100 时的概率值为：

0.0129923223383844666654513109068870692897226919075963159959911315405387765954746781823649549513027886；

当恶意节点数量为 200 时的概率值为：

0.4692855359876098354641144084770167516167561963346186017546237875587669675673670636786298382465593851。

根据运行数据，我们来绘制一张图。

中继链验证人数为 1,000，插槽数量 K=100,每个插槽分配的验证人数 T=10，其中恶意验证人数 N，那么出现事件 E：R 个以上（R=5）恶意验证人被分配到同一个平行链上的的概率 P 与 N 的关系如下：

由图可知：恶意节点在 0-100 之间，串通可能性较低，随着恶意节点超过 100，串通可能性迅速增加，当恶意节点达到 300 时，串通可能性几乎达到 100%。

波卡的共识达成过程中，有拜占庭式的 3f+1 机制，对于波卡中继链而言，恶意节点数小于 1/3，就是安全的，对于平行链而言，这个还不够，中继链恶意节点数需要小于 1/10。

当然，以上我们计算的是波卡平行链出现恶意串通的概率，100 条平行链，任意一条出现，都被计算进入了事件 E，如果单就一条特定的平行链而计，概率则要小得多。

共享安全性对 Bifrost 的影响

Bifrost 当前从 Staking 衍生品 (vToken) 切入为质押资产提供流动性，势必导致原 PoS 网络中原生资产及其对应票权在 Bifrost 协议中进行映射，通过 Bifrost 参与 Staking 的这部分原生资产所对应的共识安全也相应被转移到了 Bifrost 网络中。

如果 Bifrost 共识安全攻击成本低于原 PoS 共识安全成本，将导致黑客有意通过攻击 Bifrost 网络来完成原 PoS 网络的攻击，这将使 Bifrost 网络不再被信任，甚至遭到其他 PoS 网络的技术反制，所以只有在 Bifrost 共识安全高于或等于原 PoS 网络时， Bifrost 协议在客观条件下才能为其他 PoS 网络提供大规模的 Staking 流动性。

由于人们可以用低廉的价格从 Bifrost 平台购买投票权，并成功当选为 Validators。若这些节点作恶，则导致大量用于 Staking 的 DOT 资产被罚没，严重威胁到 Bifrost 系统的安全性。为了确保这些 Validators 不串通做恶，并确保 Polkadot 平行链与 Bifrost 自身的安全性，Bifrost 技术团队对 Polkadot 的 Slash 机制与 NPOS 规则进行了仔细调研，并设计了有效的风险防控机制。关于 Bifrost 的 Slash 风险防控机制的设计，后续文章将继续给出具体讲述和细节分析。

Bifrost 是什么？

Bifrost（彩虹桥）是波卡生态 DeFi 基础协议，致力成为质押资产提供流动性的基础设施，目前推出面向 Staking 和波卡平行链卡槽（PLO）的衍生品 vToken。目前已获得 NGC、SNZ 等机构 60 万美金种子轮融资和 Web3 基金会 Grant，同时也是 Substrate Builders Program、Web3 Bootcamp 成员。

vToken 可在 DeFi、DApp、DEX、CEX 等多场景下优化交易，通过 vToken 实现 Staking、PLO 等质押权益的转让通道，实现质押资产风险对冲，扩充场景如 vToken 作为抵押物进行借贷时，其 Staking 收益可抵销部分利息，实现低息借贷。

往期文章